Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Move Zeroes

Problem Statement

Given an array of integers nums, move all the 0s present in the array to the end while maintaining the relative order of the non-zero elements.

Note: This rearrangement should be done in-place without using extra space for another array.

Example 1:

  • Input: [1, 0, 2, 0, 3, 0, 4]
  • Expected Output: [1, 2, 3, 4, 0, 0, 0]
  • Justification: Here, all non-zero elements (1, 2, 3, 4) retain their order, and all zeros are moved to the end of the array.

Example 2:

  • Input: [0, 0, 0, 10, 20]
  • Expected Output: [10, 20, 0, 0, 0]
  • Justification: The non-zero elements (10, 20) are shifted to the front, and the zeros are relocated to the end.

Example 3:

  • Input: [5, 1, 0, 2, 0]
  • Expected Output: [5, 1, 2, 0, 0]
  • Justification: Non-zero elements (5, 1, 2) maintain their sequence, while zeros are moved to the end.

Solution

To solve this problem, we will use a two-pointer approach. The first pointer (i) will iterate over the array, and the second pointer (lastNonZeroIndex) will keep track of the position where the next non-zero element should be placed.

This approach is efficient as it allows us to perform the operation in-place, reducing the space complexity. It's also effective because it ensures that the relative order of non-zero elements is maintained by sequentially filling non-zero elements from the start. As we iterate through the array, we swap non-zero elements with the element at the lastNonZeroIndex and increment lastNonZeroIndex. This method is optimal as it requires a single pass over the array, ensuring linear time complexity.

Step-by-step algorithm

  • Initialize lastNonZeroIndex to 0.
  • Iterate through each element (i) in the array:
    • If the current element is not zero:
      • Swap the element at i with the element at lastNonZeroIndex.
      • Increment lastNonZeroIndex.
  • This process groups all non-zero elements at the beginning of the array and zeros at the end, maintaining their original order.

Algorithm Walkthrough

Let's take Example 1 [1, 0, 2, 0, 3, 0, 4]:

  • Start with lastNonZeroIndex = 0 and i = 0.
  • Iterate through the array:
    • At i = 0, element 1 is non-zero, swap it with itself, and increment lastNonZeroIndex to 1.
    • At i = 1, element 0 is zero, continue.
    • At i = 2, element 2 is non-zero, swap it with the first 0 (at index lastNonZeroIndex, which is 1), lastNonZeroIndex becomes 2.
    • At i = 3, element 0 is zero, continue.
    • At i = 4, element 3 is non-zero, swap it with the 0 (at index lastNonZeroIndex, which is 2), lastNonZeroIndex becomes 3.
    • At i = 5, element 0 is zero, continue.
    • At i = 6, element 4 is non-zero, swap it with the 0 (at index lastNonZeroIndex, which is 3), lastNonZeroIndex becomes 4.
  • Resulting array after completion: [1, 2, 3, 4, 0, 0, 0].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array, as We iterate through the array once.
  • Space Complexity: O(1), as the rearrangement is done in-place without using extra space.
Move Zeroes (easy)
Missing Ranges (easy)
Mark as Completed

On this page

Problem Statement

Example 1:

Example 2:

Example 3:

Solution

Step-by-step algorithm

Algorithm Walkthrough

Code

Complexity Analysis